package date_202405

import (
	"fmt"
	"sort"
)

//15. 三数之和
//已解答
//中等
//相关标签
//相关企业
//提示
//给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
//
//你返回所有和为 0 且不重复的三元组。
//
//注意：答案中不可以包含重复的三元组。
//
//
//
//
//
//示例 1：
//
//输入：nums = [-1,0,1,2,-1,-4]
//输出：[[-1,-1,2],[-1,0,1]]
//解释：
//nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
//nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
//nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
//不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
//注意，输出的顺序和三元组的顺序并不重要。
//示例 2：
//
//输入：nums = [0,1,1]
//输出：[]
//解释：唯一可能的三元组和不为 0 。
//示例 3：
//
//输入：nums = [0,0,0]
//输出：[[0,0,0]]
//解释：唯一可能的三元组和为 0 。
//
//
//提示：
//
//3 <= nums.length <= 3000
//-105 <= nums[i] <= 105

func threeSum(nums []int) [][]int {
	if len(nums) <= 2 {
		return [][]int{}
	}

	numsIdxMap := make(map[int][]int, len(nums))
	for idx, num := range nums {
		numsIdxMap[num] = append(numsIdxMap[num], idx)
	}

	removeDupNum := make([]int, 0, len(nums))
	for num, indexs := range numsIdxMap {
		if len(indexs) >= 3 {
			removeDupNum = append(removeDupNum, num)
			removeDupNum = append(removeDupNum, num)
			removeDupNum = append(removeDupNum, num)
		} else {
			for i := 0; i < len(indexs); i++ {
				removeDupNum = append(removeDupNum, num)
			}
		}
	}

	nums = removeDupNum
	sort.Slice(nums, func(i, j int) bool {
		return nums[i] < nums[j]
	})
	numsIdxMap = make(map[int][]int, len(nums))
	for idx, num := range nums {
		numsIdxMap[num] = append(numsIdxMap[num], idx)
	}

	sumComb := make([][]int, 0, 16)
	sumCombSet := make(map[string]struct{})
	for firstIdx := 0; firstIdx < len(nums)-2; firstIdx++ {
		for secondIdx := firstIdx + 1; secondIdx < len(nums)-1; secondIdx++ {
			expectThirdNum := 0 - nums[firstIdx] - nums[secondIdx]
			thirdNumIdxs := numsIdxMap[expectThirdNum]
			for _, thirdIdx := range thirdNumIdxs {

				if thirdIdx > secondIdx {
					comb := []int{nums[firstIdx], nums[secondIdx], nums[thirdIdx]}
					hash := fmt.Sprintf("%d_%d_%d", comb[0], comb[1], comb[2])
					_, exists := sumCombSet[hash]
					if !exists {
						sumComb = append(sumComb, comb)
						sumCombSet[hash] = struct{}{}
					}
				}
			}
		}
	}
	return sumComb
}
